package 牛客算法篇;

import java.util.List;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-02-26
 * Time:13:25
 */

/**
 *
 牛客算法篇:BM12 单链表的排序
 给定一个节点数为n的无序单链表，对其按升序排序。
 数据范围：0<n≤1000000<n≤100000，保证节点权值在[−109,109][−109,109]之内。
 要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
 示例1
 输入：
 [1,3,2,4,5]
 返回值：
 {1,2,3,4,5}
 */
public class sortInList {
    public ListNode sortInList (ListNode head) {
        // write code here
        if (head == null || head.next == null){
            return head;
        }
        //快慢指针寻找中点
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        //分割排序
        ListNode right = sortInList(slow.next);
        slow.next = null;
        ListNode left = sortInList(head);

        ListNode dummy = new ListNode(0);
        ListNode tmp = dummy;
        //对比判断
        while (left != null && right != null){
            if (left.val > right.val){
                tmp.next = right;
                tmp = tmp.next;
                right = right.next;
            }else {
                tmp.next = left;
                left = left.next;
                tmp = tmp.next;
            }
        }
        //当存在非奇数个数的时候
        tmp.next = left == null ? right : left;
        return dummy.next;
    }
}
